package _11_整理题目._5_贪心._跳跃游戏;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/jump-game/
 *
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标。
 *
 * 思路一：贪心
 *      对于数组中的任意一个位置 y，我们如何判断它是否可以到达 y ？
 *      根据题目的描述，只要存在一个位置 i，它本身可以到达，
 *      并且它跳跃的最大长度为 i + nums[i] ，这个值大于等于 y，
 *      即 i + nums[i] ≥ y，那么位置 y 可以到达。
 *
 *      这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。
 *      对于当前遍历到的位置 i，如果它在 最远可以到达的位置 的范围内，
 *      那么我们就可以从起点通过若干次跳跃到达该位置，
 *      因此我们可以用 i + nums[i] 更新 最远可以到达的位置。
 *
 *      在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，
 *      那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。
 *      反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。
 *
 */
public class _01_是否可达 {

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int maxPosition = 0;
        for (int i = 0; i < n; i++) {
            if (i <= maxPosition) {
                maxPosition = Math.max(maxPosition, i+nums[i]);
                if (maxPosition >= n-1) {
                    return true;
                }
            }
        }
        return false;
    }

    @Test
    public void main() {
        int[] nums = {2,3,1,1,4};
        int[] nums1 = {3,2,1,0,4};
        System.out.println(canJump(nums));  // true
        System.out.println(canJump(nums1)); // false
    }

}
